package nowcoderLinkList;

import java.util.ArrayList;
import java.util.List;

public class MySingleList {
    //定义节点
    class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode head;

    public void createLink() {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        /*ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        ListNode listNode5 = new ListNode(5);
        ListNode listNode6 = new ListNode(6);*/

        listNode1.next = listNode2;
        /*listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        listNode5.next = listNode6;*/
        head = listNode1;
    }

    //递归打印链表
    public void display3(ListNode pHead) {
        if (pHead == null) {
            return;
        }
        if (pHead.next == null) {
            System.out.println(pHead.val + " ");
            return;
        }
        display3(pHead.next);
        System.out.print(pHead.val + " ");
    }

    //非递归
    public void display4(ListNode newHead) {
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
    }

    //在单链表中查找关键字key是否存在
    public boolean contains(int key) {
        ListNode cur = head;
        while (cur != null) {
            if (cur.val == key) return true;
            cur = cur.next;
        }
        return false;
    }

    //得到单链表的长度
    public int size() {
        int count = 0;
        if (head == null) {
            return count;
        }
        ListNode cur = head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    //头插法
    public void addFirst(int data) {
        ListNode node = new ListNode(data);
        node.next = head;
        head = node;
    }

    //尾插法  O(N)
    public void addLast(int data) {
        ListNode node = new ListNode(data);
        ListNode cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = node;
    }

    //任意位置插入，第一个数据节点为0下标
    public void addIndex(int data, int index)
            throws ListIndexOutofException {
        checkIndex(index);
        if (index == 0) {
            addLast(data);
            return;
        }
        if (index == size()) {
            addLast(data);
            return;
        }
        ListNode node = new ListNode(data);
        ListNode cur = finIndexSubOne(index);
        node.next = cur.next;
        cur.next = node;

    }

    private ListNode finIndexSubOne(int index) {//在找到下标的位置之后进行插入
        ListNode cur = head;
        int count = 0;
        while (count != index - 1) {
            cur = cur.next;
            count++;
        }
        return cur;
    }

    //检查下标位置是否合法
    private void checkIndex(int index) {
        if (index < 0 || index > size()) {
            throw new ListIndexOutofException("下标位置不合法");
        }
    }

    //删除第一次出现关键字为key的节点
    public void remove(int key) {
        if (head.val == key) {
            head = head.next;
            return;
        }
        ListNode cur = findPrev(key);
        if (cur == null) {
            return;
        }
        cur.next = cur.next.next;
    }

    private ListNode findPrev(int key) {
        ListNode cur = head;
        while (cur.next != null) {
            if (cur.next.val == key) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

    //删除所有值为key的节点
    public void removeKey(int key) {
        if (head == null) {
            return;
        }
        ListNode cur = head.next;
        ListNode prev = head;
        while (head != null && head.val == key) {
            head = head.next;
        }
        while (cur != null) {
            if (cur.val == key) {
                prev.next = cur.next;
            } else {
                prev = cur;
            }
            cur = cur.next;
        }
    }

    //把链表置空   要保证链表中所有的节点都可以被回收
    public void clear() {
        head = null;
    }

    //1.反转链表
    public ListNode reverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return head;
        }
        ListNode cur = head.next;
        head.next = null;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        return head;
    }

    //2.链表指定区间进行反转
    public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode res = new ListNode(-1);
        res.next = head;
        ListNode prev = res;
        ListNode cur = head;
        for (int i = 1; i < m; i++) {
            prev = cur;
            cur = cur.next;
        }
        for (int i = m; i < n; i++) {
            ListNode curNext = cur.next;
            cur.next = curNext.next;
            curNext.next = prev.next;
            prev.next = curNext;
        }
        return res.next;
    }

    //3.链表中的节点每k个一组进行反转
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || head.next == null || k == 1) return head;
        ListNode res = new ListNode(-1);//定义一个头节点指向head
        res.next = head;
        ListNode pre = res;
        ListNode cur = head;
        ListNode curNext = null;
        int length = 0;
        while (head != null) {
            length++;
            head = head.next;
        }
        for (int i = 0; i < length / k; i++) {
            for (int j = 1; j < k; j++) {
                curNext = cur.next;
                cur.next = curNext.next;
                curNext.next = pre.next;
                pre.next = curNext;
            }
            pre = cur;
            cur = cur.next;
        }
        return res.next;
    }

    //4.合并两个有序的链表
    public ListNode Merge(ListNode list1, ListNode list2) {
        ListNode newHead = new ListNode(0);
        ListNode tmp = newHead;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                tmp.next = list1;
                list1 = list1.next;
            } else {
                tmp.next = list2;
                list2 = list2.next;
            }
            tmp = tmp.next;
        }
        //合并完了，list1或者list2中可能还会有数据
        if (list1 == null) {
            tmp.next = list2;
        }
        if (list2 == null) {
            tmp.next = list1;
        }
        return newHead.next;
    }

    //5.合并k和有序的链表：
    /*public ListNode mergeKLists(ArrayList<ListNode> lists) {
        ListNode newHead = new ListNode(0);
        ListNode tmp = newHead;

    }*/

    //6.判断链表中是否有环
    public boolean hasCycle(ListNode head) {
        if (head == null) return false;
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }
    //7.链表中的入口节点
    public ListNode hasCycle1(ListNode head) {
        if (head == null) return null;
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                return slow;
            }
        }
        return null;
    }
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        //相遇了
        ListNode slow = hasCycle1(pHead);
        ListNode fast = slow;
        if (slow == null) return null;
        slow = pHead;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
    //8.返回链表中倒数第k个节点
    public ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here
        int length = 0;
        ListNode cur = pHead;
        while (cur != null) {
           length++;
           cur = cur.next;
        }
        if (k <= 0 || k > length) return null;
        if (pHead == null) return null;
        ListNode fast = pHead;
        ListNode slow = pHead;
        while (k != 1) {
            fast = fast.next;
            k--;
        }
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
    //9.删除链表中的倒数第k个节点
    public ListNode removeNthFromEnd (ListNode head, int n) {
        // write code here
        ListNode res = new ListNode(0);
        res.next = head;
        ListNode prev = res;
        ListNode cur = head;
        ListNode fast = head;
        while (n != 1) {
            fast = fast.next;
            n--;
        }
        while (fast.next != null) {
            fast = fast.next;
            prev = cur;
            cur = cur.next;
        }
        prev.next = cur.next;
        return res.next;
    }
    //两个链表的第一个公共节点
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode cur1 = pHead1;
        ListNode cur2 = pHead2;
        int length1 = 0;
        int length2 = 0;
        while (cur1 != null) {
            length1++;
            cur1 = cur1.next;
        }
        while (cur2 != null) {
            length2++;
            cur2 = cur2.next;
        }
        int length = length1 - length2;
        if (length > 0) {
            while (length != 0) {
                cur1 = cur1.next;
                length--;
            }
        }else {
            while (length != 0) {
                cur2 = cur2.next;
                length++;
            }
        }
        cur1 = pHead1;
        cur2 = pHead2;
        while (cur1 != null) {
            if (cur1 == cur2) return cur1;
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return null;
    }
}
